/**
 * @file     maxWidthRamp.js
 * @brief    [962. 最大宽度坡](https://leetcode.cn/problems/maximum-width-ramp/)
 * @author   Zhu
 * @date     2024-11-28 15:42
 */

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxWidthRamp = function (nums) {
    const n = nums.length;
    let width = 0;
    const stack = [];
    const top = () => stack[stack.length - 1];

    // 从左往右，记录小值
    for (let i = 0; i < n; i++) {
        if (stack.length === 0) stack.push(i);
        else if (nums[i] < nums[top()]) {
            stack.push(i);
        }
    }
    // 从右往左，记录大值
    for (let i = n - 1; i >= 0; i--) {
        if (stack.length === 0) break;
        while (nums[i] >= nums[top()]) {
            width = Math.max(width, i - stack.pop());
        }
    }

    return width;
};

// 左边尽可能小，右边尽可能大
// [9,8,1,0,1,9,4,0,4,1]
